﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using EstructurasDeDatos;
using EstructurasDeDatos.EstructuraGrafo;

namespace Algoritmos.RutaMasCorta
{
    public class Dijkstra<T,G>
    {
        public Dijkstra()
        {

        }        
        
        private T miNodoInicial;

        public T NodoInicial
        {
            get { return miNodoInicial; }
            set { miNodoInicial = value; }
        }

        private T niNodoFinal;

        public T NodoFinal
        {
            get { return niNodoFinal; }
            set { niNodoFinal = value; }
        }

        private Hashtable dist = new Hashtable();
        private Hashtable ruta = new Hashtable();
        private Hashtable medios = new Hashtable();

        private Grafo<T, G> miGrafo;

        public Grafo<T, G> Grafo
        {
            get {
                if (miGrafo == null)
                {
                    miGrafo = new Grafo<T, G>();
                }
                return miGrafo; 
            }
            set { miGrafo = value; }
        }   
        
        public List<NodoGrafo<T,G>> Calcular()
        {            

            IniciarTablas();		// inicializa las tablas de ruta y distancia

            ListaNodos<T> nodes = Grafo.Nodos;	// nodos == Q

            /**** START DIJKSTRA ****/
            while (nodes.Count > 0)
            {
                NodoGrafo<T, G> u = ObtenerMinimo(nodes);		// obtener el nodo minimo
                nodes.Remove(u);			// remover del conjunto Q
                    
                // itere a traves de todos los vecinos
                if (u.Vecinos != null)
                    for (int i = 0; i < u.Vecinos.Count; i++)
                    {
                        NodoGrafo<T, G> vecino = (NodoGrafo<T, G>)u.Vecinos[i];
                        Relax(u.Valor, u.Vecinos[i].Valor, vecino, u.Costos[i]);		// relax each edge
                    }
            }	// repita hasta que Q este vacio
            /**** END DIJKSTRA ****/

            
            List<NodoGrafo<T, G>> retorno = new List<NodoGrafo<T, G>>();            
            T current = NodoFinal, prev = default(T);
            int contador = 0;
            do
            {
                
                prev = current;
                if (contador == 0)
                {
                    NodoGrafo<T, G> nodoTemp1 = new NodoGrafo<T, G>(prev);
                    retorno.Add(nodoTemp1);
                }
                contador++;
                T cabecera = (T)ruta[current];
                G medio = (G)medios[current];
                NodoGrafo<T, G> nodoTemp = new NodoGrafo<T, G>(cabecera, medio);
                current = nodoTemp.Valor;                   
                retorno.Add(nodoTemp);
            } while (!current.Equals(NodoInicial));
            //hace falta implementar el metodo de arriba
            return retorno;
        }

        /// <summary>
        /// ESte metodo hace 
        /// </summary>
        private void IniciarTablas()
        {            
            foreach (T cname in Grafo)
            {
                dist.Add(cname, Double.MaxValue);
                ruta.Add(cname, null);
                medios.Add(cname, null);
            }

            
            dist[this.NodoInicial] = (Double)0;
        }


        /// <summary>
        /// 
        /// </summary>
        /// <param name="nodos"></param>
        /// <returns></returns>
        private NodoGrafo<T, G> ObtenerMinimo(ListaNodos<T> nodos)
        {
            // Encontrar el nodo entre los nodos con la minima distancia
            Double minDist = Double.MaxValue;
            NodoGrafo<T, G> minNode = null;
            foreach (NodoGrafo<T, G> n in nodos)
            {
                if (((Double)dist[n.Valor]) <= minDist)
                {
                    minDist = (Double)dist[n.Valor];
                    minNode = n;
                }
            }
            return minNode;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="uCity"></param>
        /// <param name="vCity"></param>
        /// <param name="cost"></param>
        private void Relax(T uCity, T vCity, NodoGrafo<T, G> nodo, Double cost)
        {
            Double distTouCity = (Double)dist[uCity];
            Double distTovCity = (Double)dist[vCity];

            if (distTovCity > distTouCity + cost)
            {
                // update distance and route
                dist[vCity] = distTouCity + cost;
                ruta[vCity] = uCity;
                medios[vCity] = nodo.Medio;
            }
        }



    }
}
